Transportation network (graph theory)

A transportation network is a type of directed, weighted graph or network.

Transportation networks are used to model the flow of commodity, information, or traffic (see transport network).

In the 1920s A.N. Tolstoi was one of the first to study the transportation problem mathematically. In 1930, in the collection Transportation Planning Volume I for the National Commissariat of Transportation of the Soviet Union, he published a paper "Methods of Finding the Minimal Kilometrage in Cargo-transportation in space".^[1][2]

Definitions

A transportation network G is a graph with

• Exactly one vertex of in-degree 0 (no incoming edges or arcs), called the source;
• Exactly one vertex of out-degree 0 (no outgoing arcs), called the sink;
• Non-negative weight, called capacity assigned to each arc.

Flows represent commodity flowing along arcs from the source to the sink. The amount of flow along each arc may not exceed the arc's capacity, and none of the commodity may be 'lost' along the way (that is, the total flow out of the source must equal the total flow into the sink).

A cut in a network is a partition of its vertices into two sets, S and T, such that the source is in S and the sink is in T.

The cut set is the set of all arcs that connect some vertex in S with some vertex in T.

References

See also

• Spatial network
• Graph theory